#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
typedef long long LL;
using namespace std;
const LL MAXN=1e6+7;
bool isP[MAXN];
LL prime[MAXN], p_cnt=0;
LL phi[MAXN];
void Euler() {
    memset(isP, true, sizeof(isP));
    phi[1]=1;
    for (LL i=2; i<MAXN; ++i) {
        if (isP[i]) {
            phi[i]=i-1;
            prime[p_cnt++] = i;
        }
        for (LL j=0; j<p_cnt&&i*prime[j]<MAXN; ++j) {
            if (i%prime[j]==0) {
                isP[i*prime[j]]=false;
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            }
            else {
                isP[i*prime[j]]=false;
                phi[i*prime[j]] = phi[i] * (prime[j]-1);
            }
        }
    }
}
LL Phi(LL ask) {
    if (ask<MAXN) {
        return phi[ask];
    }
    LL res=1;
    for (LL i=0; i<p_cnt&&ask!=1; ++i) {
        if (ask%prime[i]==0) {
            res*=(prime[i]-1);
            ask/=prime[i];
            while (ask%prime[i]==0) {
                ask/=prime[i];
                res*=prime[i];
            }
        }
    }
    if (ask!=1) return res*=(ask-1);
    return res;
}
LL POW(LL k, LL n, LL m) {
    LL res=1;
    k%=m;
    while (n) {
        if (n&1) {
            res=(res*k)%m;
        }
        k=(k*k)%m;
        n=(n>>1);
    }
    return res;
}
LL fnl(LL a, LL b) {
    if (b==1) return 0;
    if (a==1) return 1%b;
    if (a==2) return 2%b;
    if (a==3) return 9%b;
    if (a==4) return 262144%b;
    LL t=Phi(b);
    LL z=fnl(a-1, t);
    return POW(a, z+t, b);
}
int main(int argc, char** argv) {
    #ifdef hai
    freopen("in.txt", "r", stdin);
    #endif
    Euler();
    LL a,b;
    while (cin>>a>>b) {
        cout<<fnl(a,b)<<endl;
    }
    return 0;
}
